package a09_贪心算法;

import java.util.Arrays;

/**
 * <p>
 * a17_用最少数量的箭引爆气球复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/1/16
 */
public class a17_用最少数量的箭引爆气球复习1 {
    public int findMinArrowShots(int[][] points) {
        //左边界排序
        points = Arrays.stream(points)
                .sorted((item1,item2) -> {
                    if (item1[0] > item2[0]) {
                        return 1;
                    }else if(item1[0] < item2[0]) {
                        return -1;
                    }else {return 0;}
                })
                .toArray(int[][]::new);

        int result = 1;
        for (int i = 1; i < points.length; i++) {
            if(points[i][0] > points[i-1][1]){//如果i的左边界 > i-1的右边界，说明不重叠 result++
                result++;
            }else {//重叠 为啥重叠要更新右边界
                //         1  2  3  4  5  6  7
                //第一个是  |-----|
                //第二个是     |-----|
                //第三个是       |------|
                //如果1和2没有重叠，第3个的左边界一定大于第2的左边界，所以一定大于第1个的右边界
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }
        return result;
    }
}
